1. Field of the Invention
The present invention relates generally to communication devices, and specifically, to admission control, queue management, and shaping/scheduling of flows in such communication devices.
2. Background Information
Small and medium businesses typically have networks comprised of local area networks (xe2x80x9cLANsxe2x80x9d), ranging between 10 Mega-bits per second (xe2x80x9cMbpsxe2x80x9d) to 100 Mbps, that carry information between stations for a wide range of applications. The applications can include a mixture of voice, video, interactive, web browsing, file transfers, etc., each of which has different requirements for bandwidth, latency, jitter, and data loss to ensure quality communication. The internal office LANs can either provide sufficient bandwidth or are economically upgradable to provide an order of magnitude increase in bandwidth.
The connection to a wide area network (xe2x80x9cWANxe2x80x9d) is however another matter. The bandwidth is not easily upgradable due to the cost of WAN access circuits. Various queuing techniques have been employed in WAN access equipment in attempts to provide sharing of the limited circuit bandwidth among the different types of data. These queuing techniques typically have limited applications and undesirable characteristics. For example, in one queuing technique, queues are serviced in strict priority order, which tends to starve low priority data types. Another technique, called Weighted Fair Queuing (xe2x80x9cWFQxe2x80x9d) solves the starvation effects. However, WFQ is computationally intensive, exhibits short term xe2x80x9cunfairnessxe2x80x9d, and does not provide guaranteed bandwidth, delay bound, or jitter bound characteristics for data types that need these characteristics.
The present invention is a method and apparatus for providing shaping/scheduling for flows. In one embodiment, a method of shaping/scheduling flows includes determining an arrival rate of a data unit associated with a flow, transferring the flow in a peak rate queue if the data unit arrives at a greater rate than a permissible peak rate, transferring the flow in an allocated rate queue if the data unit arrives at a greater rate than an allocated rate but less than the permissible peak rate; or otherwise transferring the flow in an output queue if the data unit arrives at a rate less than the allocated rate.